#include <bits/stdc++.h>

using namespace std;

int data1[1000001];

int main() {
    int n,temp;
    data1[1] = 1;data1[2] = 2;
    for(int i = 3;i < 1000001;i++) {
        data1[i] = (2*data1[i-1] %32767 + data1[i-2]%32767)%32767;
    }
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> temp;
        cout << data1[temp] << endl;
    }
}